#include <iostream>
#include <vector>
#include <climits>
#include <iomanip>

using namespace std;

class FloydWarshall 
{
private:
    vector<vector<int>> dist;  // 存储最短距离
    vector<vector<int>> next;  // 存储路径中的下一个顶点
    // next数组用于存储: 对于每一个节点的下一个节点
    int n;  // 顶点数量
    // 其实就是给每一个节点编了一个从0到n-1的编号
    // 这便是邻接矩阵的基本原理

public:
    FloydWarshall(int vertices) : n(vertices) 
    {
        // 初始化距离矩阵
        dist.resize(n, vector<int>(n, INT_MAX));
        next.resize(n, vector<int>(n, -1));
        
        // 对角线元素设为0
        for (int i = 0; i < n; i++) 
        {
            dist[i][i] = 0;
            next[i][i] = i;
        }
    }
    
    // 添加边，
    void addEdge(int u, int v, int weight) 
    {
        // 需要判断边是否超出范围
        if (u >= 0 && u < n && v >= 0 && v < n) 
        {
            dist[u][v] = weight;
            next[u][v] = v;
        }
    }
    
    // 执行弗洛伊德算法
    void execute() 
    {
        // 三重循环：中间顶点k，起点i，终点j
        for (int k = 0; k < n; k++) 
        {
            for (int i = 0; i < n; i++) 
            {
                for (int j = 0; j < n; j++) 
                {
                    // 避免整数溢出，否则距离会变为负数
                    if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX) 
                    {
                        if (dist[i][j] > dist[i][k] + dist[k][j]) 
                        {
                            dist[i][j] = dist[i][k] + dist[k][j];
                            next[i][j] = next[i][k];        // 这里无法理解
                        }
                    }
                }
            }
        }
    }
    
     
    // 检查是否存在负权环,重要性类似于判空
    bool hasNegativeCycle() 
    {
        for (int i = 0; i < n; i++) 
        {
            if (dist[i][i] < 0) 
            {
                return true;
            }
        }
        return false;
    }
    
    // 获取最短距离 ,这里相当于C#中的get方法，就是一个接口 
    int getShortestDistance(int u, int v) 
    {
        if (u >= 0 && u < n && v >= 0 && v < n) 
        {
            return dist[u][v];
        }
        return INT_MAX;
    }
    
    // 获取最短路径
    vector<int> getShortestPath(int u, int v) 
    {
        vector<int> path;
        
        if (u < 0 || u >= n || v < 0 || v >= n || dist[u][v] == INT_MAX) 
        {
            return path;  // 返回空路径
        }
        
        // 这里不理解这个path数组的作用
        int current = u;
        path.push_back(current);
        
        // 只要没到地方就一直找吗？？？
        while (current != v) 
        {
            current = next[current][v];
            path.push_back(current);
        }
        
        return path;
    }
    
    // 打印距离矩阵
    void printDistanceMatrix() 
    {
        cout << "距离矩阵:" << endl;
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                if (dist[i][j] == INT_MAX) 
                {
                    cout << setw(4) << "INF";
                } 
                else 
                {
                    cout << setw(4) << dist[i][j];
                }
            }
            cout << endl;
        }
    }
    
    // 打印所有最短路径
    void printAllShortestPaths() 
    {
        cout << "\n所有顶点对之间的最短路径:" << endl;
        for (int i = 0; i < n; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                // 邻接矩阵中注意自己不能自己找自己
                // 注意两个之间距离不可以是正无穷
                if (i != j && dist[i][j] != INT_MAX) 
                {
                    vector<int> path = getShortestPath(i, j);
                    cout << "从 " << i << " 到 " << j << ": 距离 = " << dist[i][j] 
                         << ", 路径 = ";
                    for (size_t k = 0; k < path.size(); k++) 
                    {
                        cout << path[k];
                        if (k < path.size() - 1) cout << " -> ";
                    }
                    cout << endl;
                }
                // 但是如果距离是正无穷的话，没有对应标识方法
            }
        }
    }
};

// 示例用法
int main() {
    // 创建包含5个顶点的图
    FloydWarshall fw(5);
    
    // 添加边（有向图）
    fw.addEdge(0, 1, 3);
    fw.addEdge(0, 2, 8);
    fw.addEdge(0, 4, -4);
    fw.addEdge(1, 3, 1);
    fw.addEdge(1, 4, 7);
    fw.addEdge(2, 1, 4);
    fw.addEdge(3, 0, 2);
    fw.addEdge(3, 2, -5);
    fw.addEdge(4, 3, 6);
    
    // 执行弗洛伊德算法
    fw.execute();
    
    // 为什么在执行之后检查负权？？？
    // 检查负权环
    if (fw.hasNegativeCycle()) 
    {
        cout << "警告：图中存在负权环！" << endl;
    } 
    else 
    {
        cout << "图中不存在负权环" << endl;
    }
    
    // 打印结果
    fw.printDistanceMatrix();
    fw.printAllShortestPaths();
    
    // 查询特定路径
    cout << "\n查询特定路径:" << endl;
    int from = 0, to = 3;
    int distance = fw.getShortestDistance(from, to);
    vector<int> path = fw.getShortestPath(from, to);
    
    if (distance != INT_MAX) 
    {
        cout << "从 " << from << " 到 " << to << " 的最短距离: " << distance << endl;
        cout << "路径: ";
        for (size_t i = 0; i < path.size(); i++) 
        {
            cout << path[i];
            if (i < path.size() - 1) cout << " -> ";
        }
        cout << endl;
    } 
    else 
    {
        cout << "从 " << from << " 到 " << to << " 没有路径" << endl;
    }
    
    return 0;
}